
public class HeapSort {

    public static void main(String[] args) {
        final HeapSort heapSort = new HeapSort();
        final Integer[] integers = {
                3, 7, 4, 2, 1, 8, 5, 0
        };
        heapSort.sort(integers);
        for (Integer integer : integers) {
            System.out.print(integer + "\t");
        }
    }

    public <T extends Comparable<T>> void sort(T[] array) {
        sort(array, array.length);
    }

    public <T extends Comparable<T>> void sort(T[] array, int length) {
        if (length <= 1) {
            return;
        }
        // 首先是寻找最大堆
        for (int i = length/2-1; i >= 0 ; i--) {
            // 如果
            buildHeap(array, i, length);
        }
        // 拿到了最大堆了,交换头节点和尾节点
        T temp = array[0];
        array[0] = array[length - 1];
        array[length - 1] = temp;
        sort(array, length - 1);
    }

    private <T extends Comparable<T>> void buildHeap(T[] arr, int i, int length) {
        int left = (i+1) * 2 - 1;
        int right = (i+1) * 2;
        // 当前节点和两个子节点哪个更大？
        int max = i;
        if (left < length && arr[left].compareTo(arr[max]) > 0) {
            max = left;
        }
        if (right < length && arr[right].compareTo(arr[max]) > 0) {
            max = right;
        }
        // 交换max和i
        if (max != i) {
            T temp = arr[max];
            arr[max] = arr[i];
            arr[i] = temp;
        }
    }

}
